/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    int* answer = (int *)malloc(numsSize * sizeof(int));
    int presum = 1, sum = 1;
    for (int j = 1; j < numsSize; j++)
        sum *= nums[j];
    for (int i = 0; i < numsSize; i++)
    {
        answer[i] = presum * sum;
        presum *= nums[i];
        if (i == numsSize - 1)
            sum = 1;
        else
        {
            if (nums[i + 1] == 0)
            {
                sum = 1;
                for (int j = i + 2; j < numsSize; j++)
                    sum *= nums[j];
            }
            else
                sum = sum / nums[i + 1];
        }
    }
    *returnSize = numsSize;

    return answer;
}